// https://www.lintcode.com/problem/can-place-flowers/

public class Solution {
    /**
     * @param flowerbed: an array
     * @param n: an Integer
     * @return: if n new flowers can be planted in it without violating the no-adjacent-flowers rule
     */
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        // Write your code here
        /*
        偶数个0的情况：
        1. 开始 - 0000 - 满 -> 开始 - X0X0 - 满 n / 2
        2. 开始 - 0000 - 结束 -> 开始 - X0X0 - 结束 n / 2
        3. 满 - 0000 - 满 -> 满 - 0x00 - 满 (n - 2) / 2
        奇数个0的情况：
        1. 开始 - 00000 - 满 -> 开始 - X0X00 - 满 (n - 1) / 2
        2. 开始 - 00000 - 结束 -> 开始 - X0X0X - 满 (n + 1) / 2
        3. 满 - 00000 - 满 -> 满 - 0x0X0 - 满 (n - 1) / 2
        4. 满 - 00000 - 结束 -> 满 - 0x0X0 - 结束 (n - 1) / 2
        头尾如果0，就补一个0方便统一处理，最后总结公式如下：
        - 偶数：(n - 1) / 2
        - 奇数：(n - 1) / 2
        */
        if (flowerbed.length == 0) {
            return false;
        }
        List<Integer> nb = new ArrayList<>();
        if (flowerbed[0] == 0) {
            nb.add(0);
        }
        for (int i : flowerbed) {
            nb.add(i);
        }
        if (flowerbed[flowerbed.length - 1] == 0) {
            nb.add(0);
        }
        int ret = 0, zs = 0;
        for (int i = 0; i <= nb.size(); ++i) { // 方便处理最后一个0
            if ((i < nb.size()) && (nb.get(i) == 0)) {
                ++zs;
            } else {
                ret += (zs - 1) / 2;
                zs = 0; // 重新计算多少个连续0
            }
        }
        return ret >= n;
    }
}